package club.xiaojiawei.array;

import java.util.Arrays;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 6/15/22 1:00 AM
 * @question 189. 轮转数组
 * @description 给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
 */
public class Rotate189 {

    public static void main(String[] args) {
        Rotate189 test = new Rotate189();
        int[] ints = {1,2,3,4,5,6,7};
        test.rotate3(ints, 3);
        System.out.println(Arrays.toString(ints));
    }

    /**
     * 递归
     * @param nums
     * @param k
     */
    public void rotate(int[] nums, int k) {
        if (k == 0){
            return;
        }
        boolean[] sign = new boolean[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if (!sign[i]){
                reversion(nums, sign, k, (i + k) % nums.length, nums[i]);
            }
        }
    }

    public void reversion(int[] nums, boolean[] sign, int k, int index, int n){
        if (sign[index]){
            return;
        }
        sign[index] = true;
        reversion(nums, sign, k, (index + k) % nums.length,nums[index]);
        nums[index] = n;
    }

    /**
     * 遍历
     * @param nums
     * @param k
     */
    public void rotate2(int[] nums, int k) {
        int length = nums.length;
        int[] ints = new int[length];
        for (int i = 0; i < length; i++) {
            ints[(i + k) % length] = nums[i];
        }
        System.arraycopy(ints, 0, nums, 0, length);
    }

    /**
     * 官方-环状替换（存疑）
     * 时间复杂度：O(n)
     * 时间复杂度：O(1)
     * @param nums
     * @param k
     */
    public void rotate3(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        int count = gcd(k, n);
        for (int start = 0; start < count; ++start) {
            int current = start;
            int prev = nums[start];
            do {
                int next = (current + k) % n;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
            } while (start != current);
        }
    }

    public int gcd(int x, int y) {
        return y > 0 ? gcd(y, x % y) : x;
    }

    /**
     * 官方-数组翻转
     * 时间复杂度：O(n)
     * 时间复杂度：O(1)
     * @param nums
     * @param k
     */
    public void rotate4(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }

    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start += 1;
            end -= 1;
        }
    }
}
